package club.xiaojiawei.linkedlist;

import java.util.HashSet;
import java.util.Objects;

/**
 * @author 肖嘉威
 * @version 1.0
 * @date 2022/4/24 下午11:18
 * @question 142.环形列表II
 * @description 给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
 * 如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 -1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
 * 不允许修改 链表
 */
public class AnnularLinkedListII142 {

    public static void main(String[] args) {
        ListNode listNode = new ListNode(2);
        ListNode head = new ListNode(1);
        head.next = listNode;
        head.next.next = new ListNode(3);
        head.next.next.next = new ListNode(4);
        head.next.next.next.next = listNode;
//        ListNode result = detectCycle(head);
        ListNode result = detectCycle2(head);
        System.out.println(result);
    }

    /**
     * HashSet检查是否重复
     * @param head
     * @return
     */
    public static ListNode detectCycle(ListNode head) {
        ListNode temp = head;
        HashSet<ListNode> set = new HashSet<>();
        while (temp != null){
            if (set.contains(temp)){
                return temp;
            }else {
                set.add(temp);
            }
            temp = temp.next;
        }
        return null;
    }

    /**
     * 双指针-通过自己画图找规律发现与官方解法思路一致
     * @param head
     * @return
     */
    public static ListNode detectCycle2(ListNode head) {
        if (head == null || head.next == null){
            return null;
        }
        ListNode tempPre = head;
        ListNode tempNext = head;
        try {
            do{
                tempPre = tempPre.next;
                tempNext = tempNext.next.next;
            }while (!Objects.equals(tempPre, tempNext));
        }catch (NullPointerException e){
//            发生空指针异常说明不是环形链表，直接返回null(可以不用catch捕获，但是需要用if语句判断是否为null，图省事所以用了catch)
            return null;
        }
//        能到这一步，说明是环形链表且两指针已相遇
        tempPre = head;
//        继续双指针，一个从相遇节点开始，另一个从头节点开始，然后再次相遇的节点就是目的节点
        while (!Objects.equals(tempPre, tempNext)){
            tempPre = tempPre.next;
            tempNext = tempNext.next;
        }
        return tempPre;

    }

    static class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }

        @Override
        public String toString() {
            return "ListNode{" +
                    "val=" + val +
                    '}';
        }
    }
}
